package com.ting.test.algorithms.查找算法.归并查找;

/**
 * 归并算法的核心思想是，
 * 将一个数组切分成两部分，分别排序后，再组合
 * 组合的时间复杂度是O(n)
 */
public class 递归实现 {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 34, 6, 7, 8, 9, 0, 11, 21, 32, 12, 4, 5, 6, 8, 9, 18, 1};
        int[] result = func(arr, 0, arr.length - 1);
        System.out.println(result);
    }

    /**
     * func的功能是，把数组arr在[L，R]位置上排有序
     *
     * @param arr
     * @param L
     * @param R
     * @return
     */
    private static int[] func(int[] arr, int L, int R) {
        if (null == arr || arr.length == 1) {
            return arr;
        }
        if (L == R) {
            return arr;
        }
        int M = L + ((R - L) >> 1);
//        int M = (L + R) / 2;
        func(arr, L, M);
        func(arr, M + 1, R);
        return merge(arr, L, R, M);
    }

    /**
     * 合并的思想是，
     * 一个元素只操作一次，谁小先放谁，一样大的，先放左边的
     *
     * @return
     */
    private static int[] merge(int[] arr, int L, int R, int M) {
        int[] help = new int[R - L + 1];
        int LIndex = L;
        int RIndex = M + 1;
        int index = 0;
        while (LIndex <= M && RIndex <= R) {
            help[index++] = arr[LIndex] <= arr[RIndex] ? arr[LIndex++] : arr[RIndex++];
        }
        //当程序走到这时，要么左边排完了，要么右边排完了，要么都拍完了，总之 后面两个循环，最多只可能执行一个
        while (LIndex <= M) {
            help[index++] = arr[LIndex++];
        }

        while (RIndex <= R) {
            help[index++] = arr[RIndex++];
        }

        for (int i=0;i<help.length; i++) {
            arr[L++] = help[i];
        }
        return arr;
    }
}
